package 递归;

public class Fib {
	
	public static void main(String[] args) {
		System.out.println(fib5(6));
	}
	
	public static int fib0(int n) {
		if (n <= 2) {
			return 1;
		}
		return fib0(n - 1) + fib0(n - 2);
	}
	
	public static int fib1(int n) {
		if (n <= 2) return 1;
		int[] array = new int[n + 1];
		array[1] = 1;
		array[2] = 1;
		return fib1(n, array);
	}
	
	private static int fib1(int n, int[] array) {
		if (array[n] == 0) {
			array[n] = fib1(n - 1, array) + fib1(n - 2, array);
		}
		return array[n];
	}
	
	public static int fib2(int n) {
		if (n <= 2) return 1;
		int[] array = new int[n + 1];
		array[1] = array[2] = 1;
		for (int i = 3; i <= n; i++) {
			array[i] = array[i - 1] + array[i - 2];
		}
		return array[n];
	}
	
	public static int fib3(int n) {
		if (n <= 2) return 1;
		int[] array = new int[]{1, 1};
		for (int i = 3; i <= n; i++) {
			array[i & 1] = array[(i - 1) & 1] + array[(i - 2) & 1];
		}
		return array[n & 1];
	}
	
	public static int fib4(int n) {
		if (n <= 2) return 1;
		int first = 1;
		int second = 1;
		for (int i = 3; i <= n; i++) {
			second = first + second;
			first = second - first;
		}
		return second;
	}
	
	public static int fib5(int n) {
		return fib5(n, 1, 1);
	}
	
	private static int fib5(int n, int first, int second) {
		if (n <= 1) return first;
		return fib5(n - 1, second, first + second);
	}
}
